// Copyright (C) Kumo inc. and its affiliates.
// Author: Jeff.li lijippy@163.com
// All rights reserved.
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
//
#pragma once

#include <turbo/log/logging.h>
#include <pollux/common/base/bit_util.h>
#include <pollux/common/base/exceptions.h>

namespace kumo::pollux {
    /// Circular double linked list with 6 byte pointers. Used for free list in
    /// HashStringAllocator so that we get a minimum allocation payload size of 16
    /// bytes. (12 bits for the links, 4 for trailer).
    ///
    /// NOTE: this class is not thread-safe.
    class CompactDoubleList {
    public:
        CompactDoubleList() {
            setNext(this);
            setPrevious(this);
        }

        CompactDoubleList(const CompactDoubleList &other) = delete;

        CompactDoubleList(CompactDoubleList &&other) = delete;

        void operator=(const CompactDoubleList &other) = delete;

        void operator=(CompactDoubleList &&other) = delete;

        /// Returns true if 'this' is the only element.
        bool empty() const {
            return next() == this;
        }

        /// Inserts 'entry' after 'this'
        void insert(CompactDoubleList *entry) {
            entry->setNext(next());
            entry->setPrevious(this);
            next()->setPrevious(entry);
            setNext(entry);
        }

        /// Unlinks 'this' from its list. Throws if 'this' is the only element.
        void remove() {
            POLLUX_CHECK(!empty());
            previous()->setNext(next());
            next()->setPrevious(previous());
        }

        CompactDoubleList *next() const {
            return loadPointer(nextLow_, nextHigh_);
        }

        CompactDoubleList *previous() const {
            return loadPointer(previousLow_, previousHigh_);
        }

        /// Updates links after the next() of 'this' has been moved to 'newNext'. Sets
        /// the next link of this, the previous link of 'newNext' and the previous
        /// link of the next() of the moved 'newNext'. The use case is taking the
        /// head of a free list block without a full remove of block plus reinsert of
        /// the remainder of the block.
        void nextMoved(CompactDoubleList *newNext) {
            setNext(newNext);
            POLLUX_CHECK(newNext->previous() == this);
            newNext->next()->setPrevious(newNext);
        }

    private:
        static constexpr uint8_t kPointerSignificantBits = 48;

        void setNext(CompactDoubleList *next) {
            storePointer(next, nextLow_, nextHigh_);
        }

        void setPrevious(CompactDoubleList *previous) {
            storePointer(previous, previousLow_, previousHigh_);
        }

        CompactDoubleList *loadPointer(uint32_t low, uint16_t high) const {
            return reinterpret_cast<CompactDoubleList *>(
                low | (static_cast<uint64_t>(high) << 32));
        }

        void storePointer(CompactDoubleList *pointer, uint32_t &low, uint16_t &high) {
            POLLUX_DCHECK_EQ(
                reinterpret_cast<uint64_t>(pointer) &
                ~bits::lowMask(kPointerSignificantBits),
                0);
            const uint64_t data = reinterpret_cast<uint64_t>(pointer);
            low = static_cast<uint32_t>(data);
            high = static_cast<uint16_t>(data >> 32);
        }

        // 12 bytes. Stores 2 48 bit pointers.
        uint32_t nextLow_;
        uint32_t previousLow_;
        uint16_t nextHigh_;
        uint16_t previousHigh_;
    };
} // namespace kumo::pollux
